package 动态规划;

// 1289  下降路径最小和2  很好的一道动归
public class Solution8 {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        dp = new int[n][n];
        for (int j = 0; j < n; j++) {
            dp[0][j] = grid[0][j];
        }
        for (int i = 1; i < n; i++) {
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            int idx1 = -1;
            for (int j = 0; j < n; j++) {
                int val = dp[i-1][j];
                if (val < min1) {
                    min2 = min1;
                    min1 = val;
                    idx1 = j;
                } else if (val < min2) {
                    min2 = val;
                }
            }
            for (int j = 0; j < n; j++) {
                if (j == idx1) {
                    dp[i][j] = grid[i][j] + min2;
                } else {
                    dp[i][j] = grid[i][j] + min1;
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int val : dp[n-1]) {
            ans = Math.min(ans, val);
        }
        return ans;
    }
    int[][] dp;
}
